package tree.completelyTree;

import pojo.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 功能描述:完全二叉树utils02
 *  宽度优先遍历 , 借助队列 来收集第一次出现叶子节点的标记位, 此后一旦再次出现非叶子节点, 那么就一定不是完全二叉树
 * 2024/06/09
 *
 * @author ZhangYi
 */
public class CompletelyTreeUtils02 {

    public boolean isCompletelyTree(TreeNode root){
        if (root == null){
            return true;
        }
        return process(root);
    }

    private boolean process(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        boolean leafNode = false;
        TreeNode l = null;
        TreeNode r = null;
        while (!queue.isEmpty()){
            if (leafNode && (l != null || r != null)){
                return false;
            }
            if (l == null && r!=null){
                return false;
            }

            TreeNode cur = queue.poll();
            l = cur.left;
            r = cur.right;
            if (l !=null){
                queue.add(cur.left);
            }
            if (r!=null){
                queue.add(r);
            }
            if (l == null || r ==null){
                leafNode =true;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        TreeNode treeNode = generateBalanceSearchTree();
        System.out.println(new CompletelyTreeUtils02().isCompletelyTree(treeNode));
    }

    private static TreeNode generateBalanceSearchTree() {
        TreeNode treeNode = new TreeNode(23,
                                         "1");
        treeNode.left = new TreeNode(12,
                                     "2");
        treeNode.left.left = new TreeNode(11,
                                           "4");


        treeNode.right = new TreeNode(34,
                                      "3");
        return treeNode;
    }

}
